class RandomizedSet {
    //如果用set添加和删除很方便，但是随机数无法实现，set获取是通过具体的val，无法通过随机数实现
    /**Set<Integer> set；
    set = new HashSet<>();
    return set.add(val);
    return set.remove(val);
     */
     List<Integer> list; //动态数组
     Map<Integer,Integer> hashMap;
     Random random;
    public RandomizedSet() {
        list = new ArrayList<Integer>();
        hashMap = new HashMap<Integer,Integer>();
        random = new Random();
    }
    
    public boolean insert(int val) {
        if(hashMap.containsKey(val)) {
            return false;
        }
        int index = list.size();//获取数组长度，获得下标
        list.add(val);
        hashMap.put(val,index);
        return true;
    }
    
    public boolean remove(int val) {
        if(!hashMap.containsKey(val)) {
            return false;
        }
        int index = hashMap.get(val);//通过下标获取到存储时的值
        int last = list.get(list.size()-1);//获取到最后一个元素
        list.set(index,last);//吧最后一个元素移动到该index下
        hashMap.put(last,index);
        list.remove(list.size()-1);//删除最后一个元素
        hashMap.remove(val);
        return true;
    }
    
    public int getRandom() {
        int index = random.nextInt(list.size());
        return list.get(index);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */